#include <fstream>
#include <sstream>
#include <queue>
#include "SyntenyFinder.hpp"

namespace synteny {
SyntenyFinder::SyntenyFinder(): delimiter(" "), girth(0) {
	nodePointersHashTable.set_empty_key(-3);
}

SyntenyFinder::~SyntenyFinder() {
	for(std::vector<Chromosome*>::iterator it = chromosomesPtrsVector.begin()
	; it != chromosomesPtrsVector.end(); ++it) {
		delete *it;
	}
	for(google::dense_hash_map<int,std::list<NodesList::iterator>* >::iterator it
	= nodePointersHashTable.begin()
	; it != nodePointersHashTable.end(); ++it) {
		delete it->second;
	}
}

int SyntenyFinder::loadChromosomes(std::string inputFileName) {
	std::ifstream inputFile(inputFileName.c_str());
	if (!inputFile.is_open()) {
		std::cerr << "Can't open file: " << inputFileName << std::endl;
		return 1;
	}
	for(size_t lineNumber = 0; inputFile.good(); ) {
		std::string line;
		getline(inputFile,line);
		if(line.empty()) {
			continue;
		}
		chromosomesPtrsVector.push_back(new Chromosome(lineNumber));
		for(size_t pos(0), endpos(0); endpos != std::string::npos; pos = endpos + 1) {
			int gene(0);
			endpos = line.find(delimiter,pos);
			std::string buffer;
			if (endpos != std::string::npos) {
				buffer = line.substr(pos,endpos - pos);
			}
			else {
				buffer = line.substr(pos);
			}
			if (!buffer.empty()) {
				std::istringstream(buffer) >> gene;
				if (nodePointersHashTable.bucket_size(
					nodePointersHashTable.bucket(gene)) == 0) {
					nodePointersHashTable[gene]
					= new std::list<NodesList::iterator>;
				}
				// Add gene to Chromosome
				nodePointersHashTable[gene]
				->push_back(chromosomesPtrsVector[lineNumber]->tailInsertNode(gene));
				// Add Chromosome iterator to hash table
				(*(--nodePointersHashTable[gene]->end()))->hashTableIterator
				= --nodePointersHashTable[gene]->end();
			}
		}
		++lineNumber;
	}
	inputFile.close();
	return 0;
}

void SyntenyFinder::modifySequence(size_t newGirth, size_t newSyntenyMinimalLenghtThreshold) {
	girth = newGirth;
	syntenyMinimalLenghtThreshold = newSyntenyMinimalLenghtThreshold;
//int cycleNumber = 0;
	// for every chromosome
	for(std::vector<Chromosome*>::iterator cIt = chromosomesPtrsVector.begin()
	; cIt != chromosomesPtrsVector.end(); ++cIt) {
		// for every gene in chromosome
		for(NodesList::iterator it = (*cIt)->chromosome.begin()->nextModifiedPath
		; it != --((*cIt)->chromosome.end()); it = it->nextModifiedPath) {
			if(checkForBranch(it)) {
				Cycle cycle;
				bool repeatRerouting = true;
				while(repeatRerouting && findCycle(it,cycle)) {
//std::cout << std::endl;
//std::cout << "Before rerout:" << std::endl;
//printModifiedSequences();
//++cycleNumber;
//std::cout << "Cycle found# " << cycleNumber << ": " << cycle.BFS_BeginGene
//<< " " << (*cycle.shortPathEndItList.begin())->gene << std::endl;
					repeatRerouting = rerouteCycle(cycle);
//std::cout << "After rerout: " << std::endl;
//printModifiedSequences();
				}
			}
		}
	}
//std::cout << "Result:" << std::endl;
printModifiedSequences();
	generateDotFile("result.dot");
	printSyntenyStatistics();
}

bool SyntenyFinder::checkForBranch(NodesList::iterator nodeIt) {
//std::cout << "checkForBranch: address - " << &nodeIt << ", gene - " << nodeIt->gene << ", chromosome - "
//<< nodeIt-> chromosomeID << std::endl;
//std::cout << Chromosome::BEGIN_TERMINAL << " " << Chromosome::END_TERMINAL << std::endl;
//	if(nodeIt->gene == Chromosome::BEGIN_TERMINAL || nodeIt->gene == Chromosome::END_TERMINAL) {
//		return false;
//	}
//std::cout << "Branch candidate!" << std::endl;
	int gene = nodeIt->getHeadAdjacent()->gene;
	for(std::list<NodesList::iterator>::iterator it = nodePointersHashTable[nodeIt->gene]->begin()
	; it != nodePointersHashTable[nodeIt->gene]->end(); ++it) {
//		if((*it)->nextModifiedPath->gene != gene) {
		if((*it)->getHeadAdjacent()->gene != gene) {
//std::cout << "Head branch found!" << std::endl;
			return true;
		}
	}
	gene = nodeIt->getTailAdjacent()->gene;
	for(std::list<NodesList::iterator>::iterator it = nodePointersHashTable[nodeIt->gene]->begin()
	; it != nodePointersHashTable[nodeIt->gene]->end(); ++it) {
		if((*it)->getTailAdjacent()->gene != gene) {
//std::cout << "Tail branch found!" << std::endl;
			return true;
		}
	}
	return false;
}

bool SyntenyFinder::findCycle(NodesList::iterator nodeIt, Cycle & cycle) {

//std::cout << "nodePointersHashTable[nodeIt->gene]->size(): " 
//<< nodePointersHashTable[nodeIt->gene]->size() << std::endl;

	std::list<DiscoverPath> discoverPaths;

	google::dense_hash_map<int, std::list<std::list<DiscoverPath>::iterator> > visitedNodes;
	visitedNodes.set_empty_key(-3);

	// Найти все гены с таким же номером, как у nodeIt. Начать обход найденных генов с головы и хвоста
	generatePathsBegins(discoverPaths, visitedNodes, nodeIt);
	for(size_t i = 0; i != girth; ++i) {
		bool cycleFound = discoverPathsAdjacentGene(discoverPaths, visitedNodes, cycle);
		if (cycleFound) return true;
	}
	return false;
}

void SyntenyFinder::generatePathsBegins(std::list<DiscoverPath> & discoverPaths
, google::dense_hash_map<int, std::list<std::list<DiscoverPath>::iterator> > & visitedNodes
, NodesList::iterator nodeIt) {
	for(std::list<NodesList::iterator>::iterator it = nodePointersHashTable[nodeIt->gene]->begin()
	; it != nodePointersHashTable[nodeIt->gene]->end(); ++it) {
		discoverPaths.push_back(DiscoverPath(DiscoverPath::HEAD, (*it)));
		visitedNodes[(*it)->gene].push_back(--discoverPaths.end());
		discoverPaths.push_back(DiscoverPath(DiscoverPath::TAIL, (*it)));
		visitedNodes[(*it)->gene].push_back(--discoverPaths.end());
	}
}

// Функция сначала группирует пути по последнему гену в пути с учетом знака гена и направления обследования.
// Затем обследует соседние гены каждой группы.
// Если ген был открыт раньше, то цикл найден.
bool SyntenyFinder::discoverPathsAdjacentGene(std::list<DiscoverPath> & discoverPaths
, google::dense_hash_map<int, std::list<std::list<DiscoverPath>::iterator> > & visitedNodes
, Cycle & cycle) {
	std::list<DiscoverPathGroup> discoverPathGroups;
	classifyPaths(discoverPaths, discoverPathGroups);
	for(std::list<DiscoverPathGroup>::iterator it = discoverPathGroups.begin()
	; it != discoverPathGroups.end(); ++it) {
		google::dense_hash_map<int, std::list<std::list<DiscoverPath>::iterator> > adjacentGenes;
		adjacentGenes.set_empty_key(-3);
		for(std::list<std::list<DiscoverPath>::iterator>::iterator pIt = (*it).paths.begin()
		; pIt != (*it).paths.end(); ++pIt) {
			NodesList::iterator currentGene = (*pIt)->getLastGene();
			NodesList::iterator nextGene;
			if (currentGene->gene == Chromosome::BEGIN_TERMINAL
			|| currentGene->gene == Chromosome::END_TERMINAL) {
				continue;
			}
			if((*pIt)->discoverDirection == DiscoverPath::HEAD) {
				nextGene = currentGene->nextModifiedPath;
			}
			else {
				nextGene = currentGene->previousModifiedPath;
			}
			(*pIt)->path.push_back(nextGene);
			adjacentGenes[nextGene->gene].push_back(*pIt);
		}
		for(google::dense_hash_map<int, std::list<std::list<DiscoverPath>::iterator> >::iterator aIt
		= adjacentGenes.begin(); aIt != adjacentGenes.end(); ++aIt) {
			int gene = aIt->first;
			if (visitedNodes[gene].empty()) {
				visitedNodes[gene] = aIt->second;
			}
			else {
				std::list<DiscoverPath> sp;
				std::list<DiscoverPath> lp;
				for(std::list<std::list<DiscoverPath>::iterator>::iterator spIt
				= visitedNodes[gene].begin()
				; spIt != visitedNodes[gene].end(); ++spIt) {
					DiscoverPath dp = **spIt;
					dp.trim(gene);
					sp.push_back(dp);
				}
				for(std::list<std::list<DiscoverPath>::iterator>::iterator lpIt
				= aIt->second.begin()
				; lpIt != aIt->second.end(); ++lpIt) {
					lp.push_back(**lpIt);
				}
				cycle = Cycle(gene, sp, lp);
				return true;
			}
		}
	}
	return false;
}

// Функция классифицирует пути по последнему гену пути с учетом знака гена и направления обследования.
void SyntenyFinder::classifyPaths(std::list<DiscoverPath> & discoverPaths
, std::list<DiscoverPathGroup> & discoverPathGroups) {
	for(std::list<DiscoverPath>::iterator it = discoverPaths.begin()
	; it != discoverPaths.end(); ++it) {
		std::list<DiscoverPathGroup>::iterator gIt = discoverPathGroups.begin();
		while(gIt != discoverPathGroups.end()) {
			// Проверить подходит ли путь к данной группе
			if((*it).getLastGeneNumber() == (*gIt).gene) {
				if(((*it).discoverDirection == DiscoverPath::HEAD
				&& (*it).getLastGeneOrientation() == (*gIt).geneSign)
				|| ((*it).discoverDirection == DiscoverPath::TAIL
				&& (*it).getLastGeneOrientation() == (*gIt).geneSign)) {
					(*gIt).paths.push_back(it);
					break;
				}
			}
			++gIt;
		}
		if (gIt == discoverPathGroups.end()) {
			discoverPathGroups.push_back(it);
		}
	}
}

bool SyntenyFinder::rerouteCycle(Cycle & cycle) {
//	cycle.printPaths();
	if(isLoop(cycle)) {
		return reroutLoop(cycle);
	}
	if(isWrongSigns(cycle)) {
		return changeCycleNodesSigns(cycle);
	}
	if(isReversalRearengement(cycle)) {
		return reverse(cycle);
	}
	if(isGenesLoosing(cycle)) {
		return addGenes(cycle);
	}
	if(isDifferentPaths(cycle)) {
		return removeCycle(cycle);
	}
	return false;
}

bool SyntenyFinder::isLoop(Cycle & cycle) {
	// if loop, short path last gene shold occur twice in long path gene
	int loopCandidateGene = cycle.shortPaths.begin()->getLastGene()->gene;
	int loopCandidateGeneOccurence(0);
	for(std::list<NodesList::iterator>::iterator it = cycle.longPaths.begin()->path.begin();
	it != cycle.longPaths.begin()->path.end(); ++it) {
		if((*it)->gene == loopCandidateGene) {
			++loopCandidateGeneOccurence;
		}
	}
	if(loopCandidateGeneOccurence != 1) {
//std::cout << "Loop" << std::endl;
		return true;
	}
	return false;
}

bool SyntenyFinder::isWrongSigns(Cycle & cycle) {
	std::list<NodesList::iterator>::iterator longPathIt;
	std::list<NodesList::iterator>::iterator shortPathIt;
	getPathsBranch(longPathIt, shortPathIt, cycle);
	if(shortPathIt == cycle.shortPaths.begin()->path.end()) {
//std::cout << "Wrong sign" << std::endl;
		return true;
	}
	return false;
}

bool SyntenyFinder::isReversalRearengement(Cycle & cycle) {
	// for future
	return false;
}

bool SyntenyFinder::isGenesLoosing(Cycle & cycle) {
	std::list<NodesList::iterator>::iterator longPathIt;
	std::list<NodesList::iterator>::iterator shortPathIt;
	getPathsBranch(longPathIt, shortPathIt, cycle);
	// проверить, что следующий после развилки ген на коротком пути - последний
	if(shortPathIt != cycle.shortPaths.begin()->path.end()
	&& longPathIt != cycle.longPaths.begin()->path.end()) {
		++shortPathIt;
		++longPathIt;
		if(shortPathIt == cycle.shortPaths.begin()->path.end()
		&& longPathIt != cycle.longPaths.begin()->path.end()) {
//std::cout << "Genes loosing" << std::endl;
			return true;
		}
	}
	return false;
}

bool SyntenyFinder::isDifferentPaths(Cycle & cycle) {
	std::list<NodesList::iterator>::iterator longPathIt;
	std::list<NodesList::iterator>::iterator shortPathIt;
	getPathsBranch(longPathIt, shortPathIt, cycle);
	// проверить, что следующие после развилки гены не последние
	if(shortPathIt != cycle.shortPaths.begin()->path.end()
	&& longPathIt != cycle.longPaths.begin()->path.end()) {
		++shortPathIt;
		++longPathIt;
		if(shortPathIt != cycle.shortPaths.begin()->path.end()
		&& longPathIt != cycle.longPaths.begin()->path.end()) {
//std::cout << "Different patchs" << std::endl;
			return true;
		}
	}
	return false;
}

bool SyntenyFinder::reroutLoop(Cycle & cycle) {
//	return false;
	for(std::list<DiscoverPath>::iterator it = cycle.longPaths.begin()
	; it != cycle.longPaths.end(); ++it) {
		NodesList::iterator toRemove((*it).getLastGene());
		removeNode(toRemove);
	}
	return true;
}

bool SyntenyFinder::changeCycleNodesSigns(Cycle & cycle) {
	if (pathsSignsIsChangeable(cycle.shortPaths, cycle.longPaths)) {
		changePathNodesSigns(cycle.shortPaths, cycle.longPaths);
		return true;
	}
	if (pathsSignsIsChangeable(cycle.longPaths, cycle.shortPaths)) {
		changePathNodesSigns(cycle.longPaths, cycle.shortPaths);
		return true;
	}
	return false;
}

bool SyntenyFinder::pathsSignsIsChangeable(std::list<DiscoverPath> & toChangePaths
, std::list<DiscoverPath> & pattern) {
	for(std::list<DiscoverPath>::iterator it = toChangePaths.begin()
	; it != toChangePaths.end(); ++it) {
		std::list<NodesList::iterator>::iterator spIt((*it).path.begin());
		std::list<NodesList::iterator>::iterator lpIt((*pattern.begin()).path.begin());
		while(lpIt != (*pattern.begin()).path.end()) {
			if(!canMakeNodesSignsMatched(spIt, it->discoverDirection
			, lpIt, pattern.begin()->discoverDirection)) {
				return false;
			}

			++spIt;
			++lpIt;
		}
	}
	return true;
}

void SyntenyFinder::changePathNodesSigns(std::list<DiscoverPath> & toChangePaths
, std::list<DiscoverPath> & pattern) {
	for(std::list<DiscoverPath>::iterator it = toChangePaths.begin()
	; it != toChangePaths.end(); ++it) {
		std::list<NodesList::iterator>::iterator spIt((*it).path.begin());
		std::list<NodesList::iterator>::iterator lpIt((*pattern.begin()).path.begin());
		while(lpIt != (*pattern.begin()).path.end()) {
			makeNodesSignsMatched(spIt, it->discoverDirection
			, lpIt, pattern.begin()->discoverDirection);

			++spIt;
			++lpIt;
		}
	}
}

bool SyntenyFinder::reverse(Cycle & cycle) {
	// for future
	
	return false;
}

bool SyntenyFinder::addGenes(Cycle & cycle) {
	// add genes to short cycle
	if (!canAddGenes(*cycle.shortPaths.begin(), *cycle.longPaths.begin())) {
		return false;
	}
	for(std::list<DiscoverPath>::iterator it = cycle.shortPaths.begin()
	; it != cycle.shortPaths.end(); ++it) {
		chromosomeAddGenes(*it, *cycle.longPaths.begin());
	}
//	return false;
	return true;
}

bool SyntenyFinder::canAddGenes(DiscoverPath & toChange, DiscoverPath & pattern) {
	DiscoverPath::Direction tcDir = toChange.discoverDirection;
	DiscoverPath::Direction patDir = pattern.discoverDirection;
	std::list<NodesList::iterator>::iterator tcIt(toChange.path.begin());
	std::list<NodesList::iterator>::iterator patIt(pattern.path.begin());
	while((*tcIt)->gene == (*patIt)->gene) {
		++tcIt;
		++patIt;
	}
	--tcIt;
	--patIt;
	if(tcDir == DiscoverPath::HEAD
	&& patDir == DiscoverPath::HEAD) {
		if((*tcIt)->previousModifiedPath->gene
		== (*patIt)->nextModifiedPath->gene) {
			return false;
		}
	}
	else if(tcDir == DiscoverPath::HEAD
	&& patDir == DiscoverPath::TAIL) {
		if((*tcIt)->previousModifiedPath->gene
		== (*patIt)->previousModifiedPath->gene) {
			return false;
		}
	}
	else if(tcDir == DiscoverPath::TAIL
	&& patDir == DiscoverPath::HEAD) {
		if((*tcIt)->nextModifiedPath->gene
		== (*patIt)->nextModifiedPath->gene) {
			return false;
		}
	}
	else if(tcDir == DiscoverPath::TAIL
	&& patDir == DiscoverPath::TAIL) {
		if((*tcIt)->nextModifiedPath->gene
		== (*patIt)->previousModifiedPath->gene) {
			return false;
		}
	}
	return true;
}

void SyntenyFinder::chromosomeAddGenes(DiscoverPath & toChange, DiscoverPath & pattern) {
	DiscoverPath::Direction tcDir = toChange.discoverDirection;
	DiscoverPath::Direction patDir = pattern.discoverDirection;
	std::list<NodesList::iterator>::iterator tcIt(toChange.path.begin());
	std::list<NodesList::iterator>::iterator patIt(pattern.path.begin());
	while((*tcIt)->gene == (*patIt)->gene) {
		makeSignsMatched((*tcIt),(*patIt), tcDir, patDir);
		++tcIt;
		++patIt;
	}
	int endGene = (*tcIt)->gene;
	while((*patIt)->gene != endGene) {
		chromosomeAddSingleGene((*tcIt), (*patIt), tcDir, patDir);
		++patIt;
	}
	makeSignsMatched((*tcIt),(*patIt), tcDir, patDir);
}

void SyntenyFinder::chromosomeAddSingleGene(NodesList::iterator toChangeIt
, NodesList::iterator & patternIt
, DiscoverPath::Direction toChangePathDirection
, DiscoverPath::Direction patternPathDirection) {
	// add gene
	if (toChangePathDirection == DiscoverPath::HEAD) {
		addNode(toChangeIt, patternIt->gene);
	}
	else {
		toChangeIt = toChangeIt->nextModifiedPath;
		addNode(toChangeIt, patternIt->gene);
	}
	makeSignsMatched(toChangeIt, patternIt, toChangePathDirection, patternPathDirection);
}

void SyntenyFinder::makeSignsMatched(NodesList::iterator toChangeIt
, NodesList::iterator & patternIt
, DiscoverPath::Direction toChangePathDirection
, DiscoverPath::Direction patternPathDirection) {
	if(toChangePathDirection == patternPathDirection) {
		toChangeIt->sign = patternIt->sign;
	}
	else {
		if(patternIt->sign == Node::MINUS) {
			toChangeIt->sign = Node::PLUS;
		}
		else {
			toChangeIt->sign = Node::MINUS;
		}
	}
}

bool SyntenyFinder::removeCycle(Cycle & cycle) {
	if (!canAddGenes(*cycle.shortPaths.begin(), *cycle.longPaths.begin())
	|| !canAddGenes(*cycle.longPaths.begin(), *cycle.shortPaths.begin())) {
		return false;
	}
	int cycleBeginGene(0);
	int cycleEndGene(0);
	std::list<NodesList::iterator>::iterator longPathIt;
	std::list<NodesList::iterator>::iterator shortPathIt;
	getPathsBranch(longPathIt, shortPathIt, *cycle.longPaths.begin(), *cycle.shortPaths.begin());
	--longPathIt;
	cycleBeginGene = (*longPathIt)->gene;
	cycleEndGene = cycle.shortPaths.begin()->getLastGene()->gene;
	for(std::list<DiscoverPath>::iterator it = cycle.shortPaths.begin()
	; it != cycle.shortPaths.end(); ++it) {
		deleteGenes(cycleBeginGene, cycleEndGene, *it);
	}
	for(std::list<DiscoverPath>::iterator it = cycle.longPaths.begin()
	; it != cycle.longPaths.end(); ++it) {
		deleteGenes(cycleBeginGene, cycleEndGene, *it);
	}
//	return false;
	return true;
}
void SyntenyFinder::deleteGenes(int cycleBeginGene, int cycleEndGene, DiscoverPath discoverPath) {
	std::list<NodesList::iterator>::iterator it = discoverPath.path.begin();
	while((*it)->gene != cycleBeginGene) {
		++it;
	}
	++it;
	while((*it)->gene != cycleEndGene) {
		removeNode(*it);
		++it;
	}

}

bool SyntenyFinder::canMakeNodesSignsMatched(std::list<NodesList::iterator>::iterator & toChangeIt
, DiscoverPath::Direction toChangeDirection
, std::list<NodesList::iterator>::iterator & patternIt
, DiscoverPath::Direction patternDirection) {
	if(toChangeDirection == patternDirection) {
		if((*toChangeIt)->sign != (*patternIt)->sign) {
		// Change sign
			return !(*toChangeIt)->signChanged;
		}
	}
	else {
		if((*toChangeIt)->sign == (*patternIt)->sign) {
		// Change sign
			return !(*toChangeIt)->signChanged;
		}
	}
	return true;
}

void SyntenyFinder::makeNodesSignsMatched(std::list<NodesList::iterator>::iterator & toChangeIt
, DiscoverPath::Direction toChangeDirection
, std::list<NodesList::iterator>::iterator & patternIt
, DiscoverPath::Direction patternDirection) {
	if(toChangeDirection == patternDirection) {
		if((*toChangeIt)->sign != (*patternIt)->sign) {
		// Change sign
			changeNodeSign(*toChangeIt);
		}
	}
	else {
		if((*toChangeIt)->sign == (*patternIt)->sign) {
		// Change sign
			changeNodeSign(*toChangeIt);
		}
	}
}

void SyntenyFinder::getPathsBranch(std::list<NodesList::iterator>::iterator & longPathIt
, std::list<NodesList::iterator>::iterator & shortPathIt
, Cycle & cycle) {
	longPathIt = cycle.longPaths.begin()->path.begin();
	shortPathIt = cycle.shortPaths.begin()->path.begin();
	while(shortPathIt != cycle.shortPaths.begin()->path.end()
	&& (*longPathIt)->gene == (*shortPathIt)->gene) {
		++longPathIt;
		++shortPathIt;
	}
}
void SyntenyFinder::getPathsBranch(std::list<NodesList::iterator>::iterator & longPathIt
, std::list<NodesList::iterator>::iterator & shortPathIt
, DiscoverPath & longPath, DiscoverPath & shortPath) {
	longPathIt = shortPath.path.begin();
	shortPathIt = longPath.path.begin();
	while(shortPathIt != shortPath.path.end()
	&& (*longPathIt)->gene == (*shortPathIt)->gene) {
		++longPathIt;
		++shortPathIt;
	}
}

void SyntenyFinder::removeNode(NodesList::iterator & dIt) {
	(*nodePointersHashTable[dIt->gene]).erase(dIt->hashTableIterator);
	dIt = (*chromosomesPtrsVector[dIt->chromosomeID]).eraseNode(dIt);
}

void SyntenyFinder::addNode(NodesList::iterator & cIt, int gene) {
//std::cout << "Inserted gene: " << gene <<" chromosome# " << cIt->chromosomeID << std::endl;
	cIt = chromosomesPtrsVector[cIt->chromosomeID]->insertNode(cIt, gene);
//std::cout << "cIt->gene: " << cIt->gene << std::endl;
//! Potential ERROR !
	nodePointersHashTable[gene]->push_back(cIt);
	(*(--nodePointersHashTable[gene]->end()))->hashTableIterator
	= --nodePointersHashTable[gene]->end();
//std::cout<<"*cIt->hashTableIterator == cIt: "<<(*cIt->hashTableIterator == cIt ? "true" : "false")<<std::endl;
}

void SyntenyFinder::changeNodeSign(NodesList::iterator & dIt) {
	dIt->changeSign();
}

void SyntenyFinder::printModifiedSequences() {
	std::cout << "Chromosomes:" << std::endl;
	for(std::vector<synteny::Chromosome*>::iterator cIt = chromosomesPtrsVector.begin()
	; cIt != chromosomesPtrsVector.end(); ++cIt) {
		for(NodesList::iterator it = (*cIt)->chromosome.begin()->nextModifiedPath
		; it != --((*cIt)->chromosome.end()); it = it->nextModifiedPath) {
			if(it->sign == Node::MINUS) {
				std::cout << "-";
			}
			std::cout << it->gene << " ";
		}
		std::cout << std::endl;
	}
}

void SyntenyFinder::generateDotFile(std::string dotFileName) {
	std::string colors[] = {"blue", "green", "red", "yellow", "orange", "yellowgreen"
	, "brown", "cadetblue", "chartreuse", "chocolate", "coral", "tomato", "tan"
	, "blueviolet", "cornflowerblue", "darkgoldenrod", "darkgreen", "darkorange", "forestgreen"
	, "deeppink", "gold", "goldenrod", "tan3", "black"};
	int colorNumber(0);
	std::ofstream dotFile;
	dotFile.open(dotFileName.c_str());
	dotFile << "digraph G {\n";
	dotFile << "overlap = scale;\n";

	int edgeBeginGene(0);
	int edgeEndGene(0);

	size_t currentSyntenyLenght(0);
	size_t currentOriginalPathLenght(0);
	for(std::vector<synteny::Chromosome*>::iterator cIt = chromosomesPtrsVector.begin()
	; cIt != chromosomesPtrsVector.end(); ++cIt) {
		edgeBeginGene = (*cIt)->chromosome.begin()->nextModifiedPath->gene;
		for(NodesList::iterator it = (*cIt)->chromosome.begin()->nextModifiedPath
		; it != --((*cIt)->chromosome.end()); it = it->nextModifiedPath) {
			if(nodePointersHashTable[it->gene]->size() != 1) {
				++currentSyntenyLenght;
//				NodesList::iterator nextGeneIt = ++it;
				if(checkForBranch(it)
				|| it->nextModifiedPath->gene == Chromosome::END_TERMINAL) {
					edgeEndGene = it->gene;
					if (edgeBeginGene != edgeEndGene) {
						if(currentSyntenyLenght
						>= syntenyMinimalLenghtThreshold) {
// Synteny region end found
							dotFile << edgeBeginGene
							<< " -> " << edgeEndGene 
							<< " [label=\""
							<< currentSyntenyLenght
							<< "\", color = \""
							<< colors[colorNumber]
							<< "\", fontcolor =\""
							<< colors[colorNumber]
							<< "\"];\n";
						}
						else {
// Short sharing region end found
							dotFile << edgeBeginGene
							<< " -> " << edgeEndGene 
							<< " [label=\""
							<< currentSyntenyLenght
							<< "\", color = \""
							<< colors[colorNumber]
							<< "\", fontcolor =\""
							<< colors[colorNumber]
							<< "\"];\n";
						}
					}
					edgeBeginGene = edgeEndGene;
					currentSyntenyLenght = 0;
				}
			}
			else {
//Originall region
				++currentOriginalPathLenght;
				if (it->nextModifiedPath->gene == Chromosome::END_TERMINAL
				|| nodePointersHashTable[it->nextModifiedPath->gene]->size() != 1) {
					edgeEndGene = it->gene;
					if (edgeBeginGene != edgeEndGene) {
							dotFile << edgeBeginGene
							<< " -> " << edgeEndGene 
							<< " [label=\""
							<< currentOriginalPathLenght
							<< "\", color = \""
							<< colors[colorNumber]
							<< "\", fontcolor =\""
							<< colors[colorNumber]
							<< "\"];\n";
					}
					currentOriginalPathLenght = 0;
					edgeBeginGene = edgeEndGene;
				}
			}
		}
		if(colorNumber != sizeof(colors) - 1) {
			++colorNumber;
		}
	}
	dotFile << "}\n";
	dotFile.close();
}

void SyntenyFinder::getStatistics(SyntenyStatistics & syntenyStatistics
, size_t syntenyMinimalLenghtThreshold) {

	int edgeBeginGene(0);
	int edgeEndGene(0);

	size_t genesCount(0);
	size_t syntenyGenesCount(0);
	size_t currentSyntenyLenght(0);

	double synteniesCount(0);

	for(std::vector<synteny::Chromosome*>::iterator cIt = chromosomesPtrsVector.begin()
	; cIt != chromosomesPtrsVector.end(); ++cIt) {
		edgeBeginGene = (*cIt)->chromosome.begin()->nextModifiedPath->gene;
		for(NodesList::iterator it = (*cIt)->chromosome.begin()->nextModifiedPath
		; it != --((*cIt)->chromosome.end()); it = it->nextModifiedPath) {
			++genesCount;
			if(nodePointersHashTable[it->gene]->size() != 1) {
				++currentSyntenyLenght;
				if(checkForBranch(it)
				|| it->nextModifiedPath->gene == Chromosome::END_TERMINAL) {
					edgeEndGene = it->gene;
					if (edgeBeginGene != edgeEndGene) {
						if(currentSyntenyLenght
						>= syntenyMinimalLenghtThreshold) {
// Synteny region end found
							syntenyGenesCount += currentSyntenyLenght;
							synteniesCount 
							+= double(1) / nodePointersHashTable[it->gene]->size();
						}
					}
					edgeBeginGene = edgeEndGene;
					currentSyntenyLenght = 0;
				}
			}
			else {
//Originall region
				if (it->nextModifiedPath->gene == Chromosome::END_TERMINAL
				|| nodePointersHashTable[it->nextModifiedPath->gene]->size() != 1) {
					edgeEndGene = it->gene;
					edgeBeginGene = edgeEndGene;
				}
			}
		}
	}
	syntenyStatistics.syntenyMinimalLenghtThreshold = syntenyMinimalLenghtThreshold;
	syntenyStatistics.genesCount = genesCount;
	syntenyStatistics.genesInSyntenies = syntenyGenesCount;
	syntenyStatistics.synteniesCount = size_t(synteniesCount + 0.5);
	syntenyStatistics.coverage = double(syntenyGenesCount)/genesCount;
}

void SyntenyFinder::printSyntenyStatistics() {
	SyntenyStatistics syntenyStatistics;
	size_t item(1);
	for(size_t minGenesInSynt = 2; minGenesInSynt != 20; ++minGenesInSynt) {
		getStatistics(syntenyStatistics, minGenesInSynt);
		std::cout << item<< ")" << std::endl;
		std::cout << "Syntenies count (min synteny length = "
		<< syntenyStatistics.syntenyMinimalLenghtThreshold
		<< "): " << syntenyStatistics.synteniesCount << std::endl;
		std::cout << "Coverage: " << syntenyStatistics.coverage << std::endl;
		++item;
	}
}

SyntenyFinder::DiscoverPath::DiscoverPath(Direction discoverDirection, NodesList::iterator begin)
: discoverDirection(discoverDirection) {
	path.push_back(begin);
}

Node::Sign SyntenyFinder::DiscoverPath::getLastGeneOrientation() {
	if (discoverDirection == HEAD) {
		return (* --path.end())->sign;
	}
	// discoverDirection = TAIL
	else {
		if ((* --path.end())->sign == Node::PLUS) {
			return Node::MINUS;
		}
		else {
			return Node::PLUS;
		}
	}
}

Node::Sign SyntenyFinder::DiscoverPath::getPathOrientation() {
	if (discoverDirection == HEAD) {
		return (*path.begin())->sign;
	}
	// discoverDirection = TAIL
	else {
		if ((*path.begin())->sign == Node::PLUS) {
			return Node::MINUS;
		}
		else {
			return Node::PLUS;
		}
	}
}

int SyntenyFinder::DiscoverPath::getLastGeneNumber() {
	return (* --path.end())->gene;
}
NodesList::iterator SyntenyFinder::DiscoverPath::getLastGene() {
	return * --path.end();
}

void SyntenyFinder::DiscoverPath::trim(int gene) {
	for(std::list<NodesList::iterator>::iterator it = path.begin()
	; it != path.end(); ++it) {
		if((**it).gene == gene) {
			path.erase(++it, path.end());
			break;
		}
	}
}

SyntenyFinder::DiscoverPathGroup::DiscoverPathGroup(std::list<DiscoverPath>::iterator path) {
	gene = (*path).getLastGeneNumber();
	geneSign = (*path).getLastGeneOrientation();
	paths.push_back(path);
}

void SyntenyFinder::Cycle::printPaths() {
	static int cycleNumber(0);
	std::cout << "Cycle: " << ++cycleNumber << std::endl;
	printPaths("Short paths:", shortPaths);
	printPaths("Long paths:", longPaths);
}

void SyntenyFinder::Cycle::printPaths(std::string title, std::list<DiscoverPath> & paths) {
	std::cout << title << std::endl;
	for(std::list<DiscoverPath>::iterator it = paths.begin()
	; it != paths.end(); ++it) {
		for(std::list<NodesList::iterator>::iterator nIt = (*it).path.begin()
		; nIt != (*it).path.end(); ++nIt) {
			if ((*nIt)->sign == Node::MINUS) {
				std::cout << "-";
			}
			std::cout << (*nIt)->gene << " ";
		}
		std::cout << std::endl;
	}
}
}
